package com.dmall.sort.algorithm;

/**
 * 成对插入排序
 * @author xiao1.wang
 * @date 2021/10/11 22:14
 */
@SuppressWarnings("all")
public class PairInsertionSort implements Sort {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        insertionSort(arr, arr.length);
    }

    private void insertionSort(int[] arr, int n) {
        for (int i = 1; i < n; i = i + 2) {
            int value1 = arr[i];
            int value2 = value1;
            boolean two = false;
            if (i + 1 < n) {
                value2 = arr[i + 1];
                two = true;
            }
            int max = value1;
            int min = value2;
            if (value2 > value1) {
                max = value2;
                min = value1;
            }

            int maxIndex = binarySearch(arr, i - 1, max);
            if (two) {
                int num = i - maxIndex;
                switch (num) {
                    case 2:  arr[maxIndex + 3] = arr[maxIndex + 1];
                    case 1:  arr[maxIndex + 2] = arr[maxIndex];
                        break;
                    default: System.arraycopy(arr, maxIndex, arr, maxIndex + 2, num);
                        break;
                }
                arr[maxIndex + 1] = max;
                int minIndex = binarySearch(arr, maxIndex - 1, min);
                num = maxIndex - minIndex;
                switch (num) {
                    case 2:  arr[minIndex + 2] = arr[minIndex + 1];
                    case 1:  arr[minIndex + 1] = arr[minIndex];
                        break;
                    default: System.arraycopy(arr, minIndex, arr, minIndex + 1, num);
                        break;
                }
                arr[minIndex] = min;
            } else {
                int num = i - maxIndex;
                switch (num) {
                    case 2:  arr[maxIndex + 2] = arr[maxIndex + 1];
                    case 1:  arr[maxIndex + 1] = arr[maxIndex];
                        break;
                    default: System.arraycopy(arr, maxIndex, arr, maxIndex + 1, num);
                        break;
                }
                arr[maxIndex] = max;
            }
        }
    }

    /**
     * 在数组arr的指定范围[0, r]区间查找第一个大于等于指定target的元素的索引
     * 因为数组的[0, r]索引的数据都是升序的，所以可以根据二分查找
     * 如果target比数组指定区间的所有元素都大
     * @param arr 数组
     * @param r 区间右索引
     * @param target 目标值
     * @return target应该插入到数组的索引
     */
    private int binarySearch(int[] arr, int r, int target) {
        int left = 0;
        int right = r;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] < target) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            }
        }
        return r + 1;
    }

    @Override
    public String getName() {
        return "成对插入排序";
    }

    public static void main(String[] args) {
        int[] arr = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr);
        Sort sort = new PairInsertionSort();
        sort.sort(arr);
        Sort.printArr(arr);
    }
}
